package com.sakura.动态规划;

public class Code62_不同路径 {
    public static void main(String[] args) {
        System.out.println(new Code62_不同路径().uniquePaths2(3, 7));
    }

    // 递归超时
    public int uniquePaths1(int n, int m) {
        return f1(n - 1, m - 1);
    }

    public int f1(int n, int m) {
        if (n == 0 && m == 0) {
            return 1;
        }

        int down = 0;
        int left = 0;
        if (n - 1 >= 0) {
            down = f1(n - 1, m);
        }
        if (m - 1 >= 0) {
            left = f1(n, m - 1);
        }
        return down + left;
    }

    public int uniquePaths2(int n, int m) {
        int[][] dp = new int[n][m];
        dp[n - 1][m - 1] = 1; // 终点位置
        // 行处理
        for (int i =  n - 2; i >= 0; i--) {
            dp[i][m - 1] = dp[i + 1][m - 1];
        }
        // 列处理
        for (int j = m - 2; j >= 0; j--) {
            dp[n - 1][j] = dp[n - 1][j + 1];
        }
        //  填表
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
         return dp[0][0];
    }
}
